package org.example.leetcode;

import java.util.Stack;

/**
 * @author: lynn
 * @Descript:最长有效括号，跟拼多多的区别， ()(() 如果长这样的，答案是2，不是4，拼多多是 4
 * @date: 2021/8/3 10:27
 * @version: 1.0
 */
public class LC32 {
    public static void main(String[] args) {
        LC32 lc=new LC32();
        String s=")()())";
        System.out.println(lc.getLongBacketDP(s));
    }

    //fixme 动态规划  https://www.bilibili.com/video/BV1Ct4y197M3?from=search&seid=8068610142415628533
    public int getLongBacketDP(String s){
        // dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]; 分析状态转移方程
        int[] dp=new int[s.length()];
        int max=0;
        for (int i = 1; i <s.length() ; i++) {
            char c=s.charAt(i);
            if (c==')'){ //此时，我一定找左括号，有的话，就是 i-dp[i-1]-1
                if (i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1)=='('){
                    if (i-dp[i-1]-2>=0){
                        dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2];
                    }else{
                        dp[i]=2+dp[i-1];
                    }
                }
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }


    public int getLongBacketPdd(String s){
        int count=0;
        Stack<Character> stack=new Stack<>();
        if (s=="" ||s.length()==0) return 0;
        for (int i = 0; i <s.length() ; i++) {
            if (s.charAt(i)=='('){
                stack.push('(');
            }else {
                if (stack.size()!=0&& stack.peek()=='(' &&s.charAt(i)==')' ){
                    count=count+2;
                    stack.pop();
                }
            }
        }
        return count;
    }
}
